#include "../common/TreeNode.h"

/* 二叉搜索树删除结点 */
TreeNode* remove(TreeNode* root, int num) {
    if (root == nullptr) return nullptr;
    TreeNode *cur = root, *pre = nullptr;
    while (cur != nullptr) {
        if (cur->val == num) break;
        pre = cur;
        if (cur->val < num) cur = cur->right;
        else cur = cur->left;
    }
    if (cur == nullptr) return nullptr;
    if (cur->left == nullptr || cur->right == nullptr) {
        TreeNode* child = cur->left != nullptr ? cur->left : cur->right;
        if (pre->left == cur) pre->left = child;
        else pre->right = child;
        delete cur;
    }
    else {
        TreeNode* nex = getInOrderNext(cur->right);
        int tmp = nex->val;
        remove(root, tmp);
        cur->val = tmp;
    }
    return cur;
}

/* 获取中序遍历中的下一个结点（仅适用于 root 有左子结点的情况） */
TreeNode* getInOrderNext(TreeNode* root) {
    if (root == nullptr) return root;
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}
